package com.changanw.code04;

import java.util.Arrays;

/**
 * @author changanw
 * @version ncc1.0
 * @description TODO  二分法进行运算
 * @date 2023/6/21 17:06
 */
public class code0401 {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    //判断两个数组的长度，保证第一个数组的长度小于第二个数组的长度
    if(nums1.length > nums2.length){
      //将两个数组进行交换
      int[] temp = nums1;
      nums1 = nums2;
      nums2 = temp;
    }
    int m = nums1.length;
    int n = nums2.length;
    //分割线左边的所有元素需要满足的个数 m+（n-m+1）/2;
    int totalLeft = (m + n + 1) / 2;
    //在nums1的区间[0，m] 里查恰当的分割线
    //同时保证 nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
    //既 第一个数组分割线左边的元素要小于第二个数组分割线右边的元素， 第二个数组分割线左边的元素小于第一个数组分割线右边的元素
    int left = 0;
    int right = m;
    while (left < right){
      //第一个数组分割线的位置i
      int i = left + (right - left + 1)/2;
      //第二个数组分割线的位置j
      int j = totalLeft - i;
      if (nums1[i-1] > nums2[j]){
        //此时进行下一轮的搜索，需要将right的位置进行左移，
        //区间[left,i-1]
        right = i -1;
      }else {
        //区间[i，right]
        //
        left = i;
      }
    }
    int i = left;
    int j = totalLeft - i;
    int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
    int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
    int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
    int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
    if (((m+n) % 2) == 1){
      return Math.max(nums1LeftMax,nums2LeftMax);
    }else {
      return (double) ((Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin,nums2RightMin))) /2;
    }
  }

  public static void main(String[] args) {
    code0401 test = new code0401();
    int a[] = {100001};
    int b[] = {100000};
    System.out.println(test.findMedianSortedArrays(a, b));
  }
}
